TOPICS
Search

M_22 Graph


M22Graph

The M_(22) graph, also known as the 77-graph, is a strongly regular graph on 77 nodes related to the Mathieu group M_(22) and to the Witt design. It is illustrated above in an embedding with 11-fold symmetry due to T. Forbes (pers. comm., Dec. 28, 2007).

It is distance-regular with intersection array {28,15;1,12}. It is also distance-transitive.

It is an integral graph with graph spectrum (-6)^(21)2^(55)16^1.

It can be obtained from the Witt design by selecting the 77 vectors of length 7 that contain a given symbol (arbitrarily chosen from 1-23) then eliminating that symbol from each of these vectors and renumbering. The resulting set of vectors V gives the unique size 77 Steiner system S(3,6,22) on points 1 to 22. Now consider as vertices the 77 vectors (v in V), with v_j&v_k adjacent if share no terms. The resulting graph is the M_(22) graph.

M22RelationGraph

Explicitly, the graph can be constructed by taking the following 77 words as vertices and drawing an edge for each pair of vertices that have no letters in common.

abciluabdfrsabejopabgmnqabhktvacdghpaceqrv
acfjntackmosademtuadinovadjklqaefgikaehlns
afhoquaflmpvagjsuvaglortahijmraipqstaknpru
bcdeknbcfgovbchjqsbcmprtbdgijtbdhlmobdpquv
beflqtbeghrubeimsvbfhinpbfjkmubgklpsbikoqr
bjlnrvbnostucdfimqcdjorucdlstvcefpsucegjlm
cehiotcfhklrcginrscgkqtuchmnuvcijkpvclnopq
defhjvdegoqsdeilprdfglnudfkoptdgkmrvdhiksu
dhnqrtdjmnpsefmnoregnptvehkmpqeijnquejkrst
eklouvfghmstfgjpqrfijlosfirtuvfknqsvghilqv
ghjknogimopuhjlptuhoprsviklmntjmoqtvlmqrsu

The M_(22) graph can also be obtained by vertex deletion of the neighbors of a point in the Higman-Sims graph (but is not, as claimed by van Dam and Haemers (2003), the subgraph induced by the vertex neighbors). Also note that van Dam and Haemers (2003) refer to the doubly truncated Witt graph as M_(22), calling the 77-vertex graph the "local Higman-Sims graph."


See also

Doubly Truncated Witt Graph, Gewirtz Graph, Goethals-Seidel Graphs, Higman-Sims Graph, Integral Graph, Mathieu Groups, Strongly Regular Graph, Witt Design

Explore with Wolfram|Alpha

References

Brouwer, A. E. "M22 Graph." http://www.win.tue.nl/~aeb/drg/graphs/M22.html.Brouwer, A. E. "The Uniqueness of the Strongly Regular Graph on 77 Points." J. Graph Th. 7, 455-461, 1983.DistanceRegular.org. "M_(22) Graph." http://www.distanceregular.org/graphs/m22graph.html.van Dam, E. R. and Haemers, W. H. "Which Graphs Are Determined by Their Spectrum?" Lin. Algebra Appl. 373, 139-162, 2003.

Cite this as:

Weisstein, Eric W. "M_22 Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/M22Graph.html

Subject classifications